#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;



typedef struct _NODE
{
    int m_val;
    int m_hight;
    struct _NODE* m_left;
    struct _NODE* m_right;

    _NODE(int m_val = 0, int m_hight = 0,
        struct _NODE* m_left = NULL, struct _NODE* m_right = NULL)
        : m_val(val), m_hight(hight), m_left(left), m_right(right)
    {
    }
} Node, * PNode;

int TreeHight(PNode root)
{
    int hight = -1;
    if (root != NULL)
    {
        hight = root->m_hight;
    }
    return hight;
}

// RR
PNode LeftRotate(PNode root)
{
    if (root == NULL)
    {
        return NULL;
    }

    PNode result = root->m_right;
    root->m_right = result->m_left;
    result->m_left = root;

    root->m_hight = std::max(Hight(root->m_left), Hight(root->m_right)) + 1;
    result->m_hight = std::max(Hight(result->m_left), Hight(root->m_right)) + 1;

    return result;
}

// LL
PNode RightRotate(PNode root)
{
    if (root == NULL)
    {
        return NULL;
    }

    PNode result = root->m_left;
    root->m_left = result->m_right;
    result->m_right = root;

    root->m_hight = std::max(Hight(root->m_left), Hight(root->m_right)) + 1;
    result->m_hight = std::max(Hight(result->m_left), Hight(root->m_right)) + 1;

    return result;
}

// LR
PNode LeftRightRotate(PNode root)
{
    root->m_left = LeftRotate(root->m_left);
    return RightRotate(root);
}

// RL
PNode RightLeftRotate(PNode root)
{
    root->m_right = RightRotate(root->m_right);
    return LeftRotate(root);
}

PNode FindMaxNode(PNode root)
{
    if (root == NULL)
    {
        return NULL;
    }
    while (root->m_right)
    {
        root = root->m_right;
    }
    return root;
}

PNode FindMinNode(PNode root)
{
    if (root == NULL)
    {
        return NULL;
    }
    while (root->m_left)
    {
        root = root->m_left;
    }
    return root;
}

PNode InsertNode(PNode root, int val)
{
    if (root == NULL)
    {
        root = new Node(val);
        return root;
    }

    if (val < root->m_val)
    {
        root->m_left = InsertNode(root->m_left, val);
        if (Hight(root->m_left) - Hight(root->m_right) == 2)
        {
            if (val < root->m_left->m_val)
            {
                RightRotate(root)
            }
            else
            {
                LeftRightRotate(root);
            }
        }
    }
    else
    {
        root->m_right = InsertNode(root->m_right, val);
        if (Hight(root->m_left) - Hight(root->m_right) == -2)
        {
            if (val > root->m_right->m_val)
            {
                LeftRotate(root)
            }
            else
            {
                RightLeftRotate(root);
            }
        }
    }
    // if has no rotate, it is needed
    root->m_hight = std::max(Hight(root->m_left), Hight(root->m_right)) + 1;
    return root;
}

PNode DelNode(PNode root, int val)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (val < root->m_val)
    {
        root->m_left = DelNode(root->m_left, val);
        if (Hight(root->m_left) - Hight(root->m_right) == -2)
        {
            if (Hight(root->m_right->m_left) - Hight(root->m_right->right) == 1)
            {
                root = RightLeftRotate(root);
            }
            else
            {
                root = LeftRotate(root);
            }
        }
    }
    else if (val > root->m_val)
    {
        root->m_right = DelNode(root->m_right, val);
        if (Hight(root->m_left) - Hight(root->m_right) == 2)
        {
            if (Hight(root->m_left->m_left) - Hight(root->m_left->right) == 1)
            {
                root = LeftRightRotate(root);
            }
            else
            {
                root = RightRotate(root);
            }
        }
    }
    else
    {
        if (root->m_left != NULL && root->m_right != NULL)
        {
            if (Hight(root->m_left) > Hight(root->m_right))
            {
                PNode maxNode = FindMaxNode(root->m_left);
                root->m_val = maxNode->m_val;
                root->m_left = DelNode(root->m_left, maxNode->m_val);
            }
            else
            {
                PNode minNode = FindMinNode(root->m_right);
                root->m_val = minNode->m_val;
                root->m_right = DelNode(root->m_right, minNode->m_val);
            }
        }
        else
        {
            PNode tmp = root->m_left ? root->m_left : root->m_right;
            if (tmp != NULL)
            {
                PNode del = root;
                root = tmp;
                delete del;
                del = NULL;
            }
            else
            {
                delete root;
                root = NULL;
            }
        }
    }
    if (root != NULL)
    {
        root->m_hight = std::max(Hight(root->m_left), Hight(root->m_right)) + 1;
    }
    return root;
}

void PrintTreeNoRecure_f(PNode root)
{
    if (root == NULL)
    {
        return;
    }
    PNode tmp = NULL;
    stack<PNode> s;
    s.push(root);
    while (!s.empty())
    {
        tmp = s.top();
        cout << tmp->m_val << "(" << tmp->m_hight << ");";
        s.pop();
        if (tmp->m_right != NULL)
        {
            s.push(tmp->m_right);
        }
        if (tmp->m_left != NULL)
        {
            s.push(tmp->m_left);
        }
    }
    cout << endl;
}

int main()
{
    int a[5] = { 6,3,5,8,2 };
    PNode root = NULL;
    for (int i = 0; i < 5; i++)
    {
        root = InsertNode(root, a[i]);
    }
    PrintTreeNoRecure_f(root);
    root = InsertNode(root, 4);
    PrintTreeNoRecure_f(root);
    root = InsertNode(root, 7);
    PrintTreeNoRecure_f(root);

    root = DelNode(root, 4);
    PrintTreeNoRecure_f(root);
    return 0;
} 